/*
day53
2019.10.20
*/
#define MAXSIZE 1024
#include<stdio.h>
#include<stdlib.h>
struct TreeNode{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
}; 


int** levelOrderBottom1(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{
	struct TreeNode *queue[MAXSIZE];
	int first=0,last=0;
	
	(*returnColumnSizes)=(int *)malloc(sizeof(int)*MAXSIZE); 
	int **res=(int **)malloc(sizeof(int *)*MAXSIZE);
	*returnSize=0;
	
	if(root) queue[last++%MAXSIZE]=root;
	
	
	while(first!=last)
	{
		
		(*returnColumnSizes)[*returnSize]=(last-first);
		res[*returnSize]=(int *)malloc(sizeof(int) * (*returnColumnSizes)[*returnSize]);
		
		for(int i=0;i<(*returnColumnSizes)[*returnSize];i++)
		{
			struct TreeNode *node=queue[first++%MAXSIZE];
			res[*returnSize][i]=node->val;
			if(node->left) queue[last++%MAXSIZE]=node->left;
			if(node->right) queue[last++%MAXSIZE]=node->right;
		}
		
		(*returnSize)++;
	}
	
	int *a,b;
	for(int i=0,j=(*returnSize)-1;i<j;i++,j--)
	{
		a=res[i];
		res[i]=res[j];
		res[j]=a;
		
		b=(*returnColumnSizes)[i];
		(*returnColumnSizes)[i]=(*returnColumnSizes)[j];
		(*returnColumnSizes)[j]=b;
	}
	
	return res;
} 


int main()
{
	return 0;
}
